#pragma once

template <typename Key, size_t Deg>
struct BTree;
namespace BTreeDetail
{
	template <typename Key, size_t Deg> requires MinDeg<Deg>
	struct InnNode;
	template <typename Key, size_t Deg> requires MinDeg<Deg>
	struct DataNode
	{
		using Owner = BTree<Key, Deg>;
		using POwnerPtr = std::shared_ptr<Owner*>;
		using PDataNodePtr = std::shared_ptr<DataNode*>;
		using InnNode = InnNode<Key, Deg>;
		using PInnNodePtr = std::shared_ptr<InnNode*>;
		using DataList = std::list<DataNode*>;
		using DataListIt = DataList::iterator;

		POwnerPtr _ppOwner;
		PInnNodePtr _ppParent;
		PDataNodePtr _ppSelf;
		PInnNodePtr _ppLeft;
		PInnNodePtr _ppRight;
		DataListIt _id;

		Key _k;

		DataNode(POwnerPtr ppOwner);
		virtual ~DataNode();
		auto merge()->InnNode*;
		bool verify(Owner* pOwner, InnNode* pParent);
	};

	template <typename Key, size_t Deg> requires MinDeg<Deg>
	struct InnNode
	{
		using Owner = BTree<Key, Deg>;
		using POwnerPtr = std::shared_ptr<Owner*>;
		using PDataNodePtr = std::shared_ptr<DataNode<Key, Deg>*>;
		using PInnNodePtr = std::shared_ptr<InnNode*>;
		using DataNode = DataNode<Key, Deg>;
		using DataList = std::list<DataNode*>;
		using DataListIt = DataList::iterator;

		POwnerPtr _ppOwner;
		PInnNodePtr _ppParent;
		PInnNodePtr _ppSelf;
		PDataNodePtr _ppLeft;
		PDataNodePtr _ppRight;
		bool _leaf = true;

		DataList _data;

		InnNode(POwnerPtr ppOwner);
		virtual ~InnNode();
		auto find(const Key& k)->std::pair<DataListIt, bool>;
		auto insert(const Key& k)->std::pair<DataListIt, bool>;
		auto insertNonFull(const Key& k, DataListIt it)->std::pair<DataListIt, bool>;
		auto split(const Key& k, DataListIt it)->std::pair<DataListIt, bool>;
		auto erase(const Key& k)->std::pair<DataListIt, bool>;
		auto erase(DataListIt it)->std::pair<DataListIt, bool>;

		void writeDisk() {}
		void readDisk() {}
		template <typename Func>
		auto show(std::ostream& os, Func func) const->std::ostream&;
		bool verify(Owner* pOwner, InnNode* pParent);

		auto getNextNode(DataListIt it)->InnNode*;
	};
}

#include "BTreeNodeImpl.h"
